package Graph;


public class Prim {


    public static void PRIM(int [][] graph,int start,int n){

        int [][] mins=new int [n][2];

        for(int i=0;i<n;i++){
            if(i==start){

                mins[i][0]=-1;

                mins[i][1]=0;

            }else if( graph[start][i]!=-1){

                mins[i][0]=start;

                mins[i][1]= graph[start][i];

            }else{

                mins[i][0]=-1;

                mins[i][1]=Integer.MAX_VALUE;

            }

        }

        for(int i=0;i<n-1;i++){

            int minV=-1,minW=Integer.MAX_VALUE;

            for(int j=0;j<n;j++){



                if(mins[j][1]!=0&&minW>mins[j][1]){

                    minW=mins[j][1];

                    minV=j;

                }

            }


            mins[minV][1]=0;

            System.out.println("最小生成树的第"+i+"条最小边=<"+(mins[minV][0]+1)+","+(minV+1)+">，权重="+minW);

            for(int j=0;j<n;j++){//更新mins数组

                if(mins[j][1]!=0){

//					System.out.println("MINV="+minV+"||tree[minV][j]="+tree[minV][j]);

                    if( graph[minV][j]!=-1&& graph[minV][j]<mins[j][1]){

                        mins[j][0]=minV;

                        mins[j][1]= graph[minV][j];

                    }

                }

            }

        }

    }


    public static void main(String [] args){
        int [][] tree={{2,6,4,5,5,1}, {6,5,4,1,3,4}, {-1,7,1,1,3,8}, {9,-1,2,4,-1,2}, {-1,8,4,-1,9,6}, {5,3,4,3,9,-1}};
        Prim.PRIM(tree, 0, 6);


    }



}
